Роглянуто задачі паралелізації (компактації) дії автоматів на інформаційне середовище, коли між деякими операторами існує відношення незалежності. Дані задачі формулюються у термінах вільних частково комутативних моноїдів, що моделюють інформаційне середовище. Показано, що для ациклічних автоматів задача паралелізації при певних обмеженнях може бути розв'язана за поліноміальний час.

Запропоновано ефективні алгоритми для розв'язання декількох задач входження трека-зразка в трек-об'єкт. Розглянуто задачі пошуку зразка в треку, пов'язані з задачею пошуку частих зразків в структурованих даних, та задачі обчислення числа вікон, що містять зразок.

Індекс рубрикатора НБУВ: В192.19

Рубрики:

Чисельні методи оптимізації та моделювання

Шифр НБУВ: Ж29144 Пошук видання у каталогах НБУВ 

The paper presents algorithms for solving several matching problems of Mazurkiewicz traces. These algorithms are reduced to the construction of automata that recognize the corresponding rational trace languages. Rational trace languages and their properties were studies by many authors. The paper considers trace languages related to specific problems that have analogs in stringology.

Поняття заборонених рядків та підпослідовностей, що застосовуються до рядків, узагальнені на треки. Наведено розв'язок задач побудови для заданого трека множин заборонених треків та заборонених підтреків.